package Hot_100;

import java.util.*;

//二叉树的程序遍历
public class Hot_100_102 {
    /**
     * 值域
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            left = null;
            right = null;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }

    /**
     * 二叉树索引和值定义
     */
    public static class TreeValue {
        public static int index = 0;
        public static final int[] TREE_VALUE = new int[]{3, 9, 0, 0, 20, 15, 0, 0, 7, 0, 0};
    }

    /**
     * 主函数
     *
     * @param args
     */
    //结果集
    static List<List<Integer>> ans = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TreeNode root = new TreeNode(-1);
        root = CreateTree(root, 0);
        levelOrder(root);
        for (List<Integer> t1 : ans) {
            for (int t2 : t1) {
                System.out.print(t2 + " ");
            }
            System.out.println();
        }
    }

    /**
     * 创建二叉树
     *
     * @param node
     * @param i
     * @return
     */
    public static TreeNode CreateTree(TreeNode node, int i) {
        if (TreeValue.TREE_VALUE[i] == 0) {
            return null;
        } else {
            node.setVal(TreeValue.TREE_VALUE[i]);
        }
        TreeNode leftchild = new TreeNode(-1);
        node.left = CreateTree(leftchild, ++TreeValue.index);
        TreeNode rightchild = new TreeNode(-1);
        node.right = CreateTree(rightchild, ++TreeValue.index);
        return node;
    }

    /**
     * 层序打印
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return ans;
        }
        dfs(root);
        return ans;
    }

    /**
     * dfs
     *
     * @param root
     */
    public static void dfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans.add(list);
        }
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)
